#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <algorithm>
#include <iterator>
#include <cstring>
#include <iomanip>

using namespace std;

// 产生式结构体
struct Production
{
    string left;          // 产生式左部
    vector<string> right; // 产生式右部
};

map<string, vector<int>> grammar_dict;
vector<Production> grammar;             // 产生式集合
set<string> symbols;                    // 文法所有符号集
set<string> nonterminal_symbols;        // 非终结符集合
set<string> terminal_symbols;           // 终结符集合
map<string, set<string>> FIRST;         // FIRST集合
map<string, set<string>> FOLLOW;        // FOLLOW集合
vector<set<pair<int, int>>> COLLECTION; // 项目集规范簇
vector<map<string, int>> GOTO;          // SLR分析表 GOTO部分
vector<map<string, string>> ACTION;     // SLR分析表 ACTION部分
string Begin;                           // 文法产生符号

// 读取文法
void read_grammar()
{
    fstream grammar_file("grammar.txt", std::ios::in);
    string grammar_line = "";

    if (grammar_file.is_open())
    {
        bool flag_begin = true;

        while (getline(grammar_file, grammar_line))
        {
            stringstream production(grammar_line);
            string left, arrow, right;
            getline(production, left, ' ');
            getline(production, arrow, ' ');
            getline(production, right);

            nonterminal_symbols.insert(left);

            // 处理产生式左部
            Production prod;
            prod.left = left;

            // 判断是否是开始符号
            if (flag_begin)
            {
                Begin = left;
                flag_begin = false;
            }

            // 处理产生式右部
            stringstream production_right(right);
            string right_symbols;
            if (getline(production_right, right_symbols))
            {
                stringstream ss(right_symbols);
                string symbol;
                while (getline(ss, symbol, ' '))
                {
                    prod.right.push_back(symbol);
                    symbols.insert(symbol);
                }
            }

            grammar.push_back(prod);
            grammar_dict[left].push_back(grammar.size() - 1);
        }

        symbols.insert("#");
        grammar_file.close();
    }

    else
    {
        cout << "grammar.txt file open failed." << endl;
    }

    // for (int it = 0; it < grammar.size(); it++)
    // {
    //     cout << it << '\t' << grammar[it].left << " -> "; // 左部
    //     for (int it1 = 0; it1 < grammar[it].right.size(); it1++)
    //         cout << grammar[it].right[it1] << " "; // 右部
    //     cout << endl;
    // }

    return;
}

// 计算first集合
void compute_first()
{
    int is_changed = 1;
    while (is_changed)
    {
        is_changed = 0;
        for (auto prod : grammar)
        {
            set<string> first = FIRST[prod.left];
            size_t orginal_size = first.size();

            // 若产生式右部为空则加入空串
            if (prod.right.empty())
            {
                first.insert("$");
            }
            else
            {
                int all_nullable = 1;
                // 产生式的右部
                vector<string> prod_right = prod.right;
                for (auto symbol : prod_right)
                {
                    if (!nonterminal_symbols.count(symbol))
                    {
                        first.insert(symbol);
                        all_nullable = 0;
                        break;
                    }
                    else
                    {
                        set<string> temp(FIRST[symbol].begin(), FIRST[symbol].end());
                        temp.erase("$");
                        for (auto t : temp)
                            first.insert(t);

                        if (FIRST[symbol].count("$") == 0)
                        {
                            all_nullable = 0;
                            break;
                        }
                    }
                }
                if (all_nullable)
                    first.insert("$");
            }

            if (orginal_size != first.size())
                is_changed = 1;

            FIRST[prod.left] = first;
        }
    }

    return;
}

// 计算follow集合
void compute_follow()
{
    FOLLOW[Begin].insert("#");

    int is_changed = 1;
    while (is_changed)
    {
        is_changed = 0;
        for (auto prod : grammar)
        {
            set<string> follow1 = FOLLOW[prod.left];
            // 产生式右部的符号
            vector<string> prod_right = prod.right;

            size_t size = prod_right.size();
            for (size_t i = 0; i < size; i++)
            {
                if (!nonterminal_symbols.count(prod_right[i]))
                    continue;

                // 右部符号是非终结符
                else
                {
                    set<string> follow2 = FOLLOW[prod_right[i]];
                    size_t original_size = follow2.size();
                    int all_nullable = 1;

                    for (size_t j = i + 1; j < size; j++)
                    {
                        if (nonterminal_symbols.count(prod_right[j]))
                        {
                            set<string> first(FIRST[prod_right[j]].begin(), FIRST[prod_right[j]].end());
                            first.erase("$");

                            for (auto t : first)
                                follow2.insert(t);

                            if (FIRST[prod_right[j]].count("$") == 0)
                            {
                                all_nullable = 0;
                                break;
                            }
                        }

                        else
                        {
                            follow2.insert(prod_right[j]);
                            all_nullable = 0;
                            break;
                        }
                    }

                    // 到达右部最后一个符号或者i后面的符号都能推出$时
                    if (all_nullable || i == size - 1)
                        for (auto t : follow1)
                            follow2.insert(t);

                    if (follow2.size() != original_size)
                        is_changed = 1;

                    FOLLOW[prod_right[i]] = follow2;
                }
            }
        }
    }

    return;
}

// 计算给定项目集的闭包
// (x, y) 表示点在第x条文法的第y个位置上
void closure(set<pair<int, int>> &items)
{
    int is_changed = 1;
    while (is_changed)
    {
        is_changed = 0;
        set<pair<int, int>> new_items;
        for (auto item : items)
        {
            int num = item.first, pos = item.second;
            if (pos < grammar[num].right.size())
            {
                string symbol = grammar[num].right[pos];
                if (nonterminal_symbols.count(symbol))
                {
                    for (auto idx : grammar_dict[symbol])
                    {
                        pair<int, int> new_item;
                        new_item = make_pair(idx, 0);

                        if (!items.count(new_item) && !new_items.count(new_item))
                        {
                            is_changed = 1;
                            new_items.insert(new_item);
                        }
                    }
                }
            }
        }

        for (auto t : new_items)
            items.insert(t);
    }

    return;
}

void compute_goto(set<pair<int, int>> &items, const string &symbol, set<pair<int, int>> &result)
{
    /*
        参数含义：
        items：当前项目集
        symbol：输入符号
        result：输出项目集
    */

    for (auto item : items)
    {
        int num = item.first, pos = item.second;
        if (grammar[num].right[pos] == symbol && pos < grammar[num].right.size())
        {
            pair<int, int> new_item = make_pair(num, pos + 1);
            result.insert(new_item);
        }
    }
    closure(result);

    return;
}

// 检查项目集是否包含归约项目 根据归约规则更新GOTO表
void check_repro(set<pair<int, int>> &items)
{

    // 遍历项目集 检查是否存在归约项目
    for (const auto &item : items)
    {
        const int production_index = item.first; // 产生式的索引
        const int dot_pos = item.second;         // 圆点的位置

        const auto &production_right = grammar[production_index].right;
        const string &production_left = grammar[production_index].left;

        // 如果当前项目是归约项目，即圆点在最右侧 或者 右侧为空符号
        if (dot_pos == production_right.size() ||
            (production_right[0] == "$" && dot_pos == 0))
        {

            // 获取当前产生式左部符号的FOLLOW集
            const auto &follow = FOLLOW[production_left];

            // 对FOLLOW集中的每个符号进行归约处理
            for (const auto &term : follow)
            {
                GOTO[COLLECTION.size()][term] = -production_index - 1;
            }
        }
    }
}

// 填充GOTO部分
void construct_goto()
{
    // 初始化起始项目集
    set<pair<int, int>> start_items = {{0, 0}};
    closure(start_items);
    COLLECTION.push_back(start_items);

    // 遍历项目集
    for (size_t i = 0; i < COLLECTION.size(); i++)
    {

        for (const string &symbol : symbols)
        {
            if (symbol == "$")
                continue; // 要排除掉空符号

            set<pair<int, int>> goto_items;
            compute_goto(COLLECTION[i], symbol, goto_items);

            // 新的项目集不为空 同时要求不重复
            if (!goto_items.empty())
            {
                auto it = find(COLLECTION.begin(), COLLECTION.end(), goto_items);

                // 存在重复
                if (it != COLLECTION.end())
                {
                    GOTO[i][symbol] = distance(COLLECTION.begin(), it);
                }
                else
                {
                    int newsize = COLLECTION.size() + 1;
                    GOTO.resize(newsize);
                    check_repro(goto_items); // 检查新项目集是否归约
                    COLLECTION.push_back(goto_items);
                    GOTO[i][symbol] = COLLECTION.size() - 1;
                }
            }
        }
    }
}

// 填充ACTION部分
void construct_action()
{
    for (int i = 0; i < GOTO.size(); i++)
    {
        map<string, string> action_entry; // 当前状态对应的ACTION任务

        for (const string &terminal_symbol : symbols)
        {
            if (nonterminal_symbols.find(terminal_symbol) == nonterminal_symbols.end())
            {
                int action_value = GOTO[i][terminal_symbol];

                if (action_value < 0)
                {
                    if ((-(action_value + 1)) == 0)
                    {
                        // 接受
                        action_entry[terminal_symbol] = "acc";
                    }
                    else
                    {
                        // 规约
                        action_entry[terminal_symbol] = "r" + to_string(-(action_value + 1));
                    }
                }
                else if (action_value > 0)
                {
                    // 移进
                    action_entry[terminal_symbol] = "S" + to_string(action_value);
                }
                else
                {
                    action_entry[terminal_symbol] = "";
                }
            }
        }

        ACTION.push_back(action_entry);
    }
}

// 打印SLR表 检查错误
void print_slr_table()
{
    cout << setiosflags(ios::left) << "ACTION: " << endl;
    cout << setw(5) << "状态";
    for (const string &terminal_symbol : symbols)
    {
        if (nonterminal_symbols.find(terminal_symbol) == nonterminal_symbols.end())
        {
            cout << setw(5) << terminal_symbol << " ";
        }
    }
    cout << endl;

    for (int i = 0; i < ACTION.size(); i++)
    {
        cout << setw(5) << i;
        for (const string &terminal_symbol : symbols)
        {
            if (nonterminal_symbols.find(terminal_symbol) == nonterminal_symbols.end())
            {
                cout << setw(5) << ACTION[i].at(terminal_symbol) << " ";
            }
        }
        cout << endl;
    }

    cout << setiosflags(ios::left) << "GOTO表: " << endl;
    cout << setw(5) << "状态";
    for (const string &nonterminal_symbol : symbols)
    {
        if (nonterminal_symbols.find(nonterminal_symbol) != nonterminal_symbols.end())
        {
            cout << setw(5) << nonterminal_symbol << " ";
        }
    }
    cout << endl;

    for (int i = 0; i < GOTO.size(); i++)
    {
        cout << setw(5) << i;
        for (const string &nonterminal_symbol : symbols)
        {
            if (nonterminal_symbols.find(nonterminal_symbol) != nonterminal_symbols.end())
            {
                if (GOTO[i].count(nonterminal_symbol))
                {
                    cout << setw(5) << GOTO[i].at(nonterminal_symbol) << " ";
                }
                else
                {
                    cout << setw(5) << " " << " ";
                }
            }
        }
        cout << endl;
    }
}

// 输出到文本
void slr_table_to_file(const string &filename)
{
    ofstream out_file(filename);
    if (!out_file.is_open())
    {
        cout << "无法打开" << endl;
        return;
    }

    out_file << setiosflags(ios::left) << "ACTION表：" << endl;
    out_file << setw(5) << "状态";
    for (const string &terminal_symbol : symbols)
    {
        if (nonterminal_symbols.find(terminal_symbol) == nonterminal_symbols.end())
        {
            out_file << setw(5) << terminal_symbol << " ";
        }
    }
    out_file << endl;

    for (int i = 0; i < ACTION.size(); i++)
    {
        out_file << setw(5) << i;
        for (const string &terminal_symbol : symbols)
        {
            if (nonterminal_symbols.find(terminal_symbol) == nonterminal_symbols.end())
            {
                out_file << setw(5) << ACTION[i].at(terminal_symbol) << " ";
            }
        }
        out_file << endl;
    }

    out_file << setiosflags(ios::left) << "GOTO表：" << endl;
    out_file << setw(5) << "状态";
    for (const string &nonterminal_symbol : symbols)
    {
        if (nonterminal_symbols.find(nonterminal_symbol) != nonterminal_symbols.end())
        {
            out_file << setw(5) << nonterminal_symbol << " ";
        }
    }
    out_file << endl;

    for (int i = 0; i < GOTO.size(); i++)
    {
        out_file << setw(5) << i;
        for (const string &nonterminal_symbol : symbols)
        {
            if (nonterminal_symbols.find(nonterminal_symbol) != nonterminal_symbols.end())
            {
                if (GOTO[i].count(nonterminal_symbol))
                {
                    out_file << setw(5) << GOTO[i].at(nonterminal_symbol) << " ";
                }
                else
                {
                    out_file << setw(5) << " " << " ";
                }
            }
        }
        out_file << endl;
    }

    out_file.close();
}

void parse_input(const vector<string> &tokens)
{
    stack<int> states; // 状态栈
    states.push(0);    // 起始状态

    stack<string> stack_symbols; // 符号栈
    stack_symbols.push("BOF");   // Beginning of file marker for the stack

    vector<string> input(tokens); // 输入序列
    input.push_back("#");         // End of input marker

    int ip = 0;   // Input pointer
    int step = 1; // Step counter

    ofstream output("./result-syntax/8gra.tsv"); // 将结果保存到文件

    while (true)
    {
        int current_state = states.top(); // 当前状态
        string next_token = input[ip];    // 输入token

        auto action = GOTO[current_state].find(next_token);
        if (action == GOTO[current_state].end())
        {
            output << step << "\t" << stack_symbols.top() << "#" << next_token << "\t" << "error" << endl;
            break;
        }

        int next_state = action->second;         // 下一状态
        string top_symbol = stack_symbols.top(); // 栈顶符号

        if (next_state >= 0)
        { // 移进 move
            output << step << "\t" << top_symbol << "#" << next_token << "\t" << "move" << endl;
            states.push(next_state);        // 状态进栈
            stack_symbols.push(next_token); // token进栈
            ip++;                           // 读取下一token
            step++;                         // 增加步骤编号
        }
        else if (next_state < -1)
        { // 归约 reduction
            int production_index = -next_state - 1;
            Production prod = grammar[production_index];
            int rhs_size = prod.right.size();

            if (prod.right[0] == "$")
                rhs_size = 0;

            output << step << "\t" << top_symbol << "#" << next_token << "\t" << "reduction " << endl;

            for (int i = 0; i < rhs_size; ++i)
            {
                states.pop();        // 状态出栈
                stack_symbols.pop(); // 符号出栈
            }
            stack_symbols.push(prod.left); // 归约后的非终结符进栈

            auto goto_action = GOTO[states.top()].find(prod.left);
            if (goto_action == GOTO[states.top()].end())
            {
                output << step << "\t" << stack_symbols.top() << "#" << next_token << "\t" << "error" << endl;
                break;
            }
            states.push(goto_action->second); // 状态进栈
            step++;                           // 增加步骤编号
        }
        else if (next_state == -1)
        { // Accept
            output << step << "\t" << top_symbol << "#" << next_token << "\t" << "accept" << endl;
            break;
        }
    }

    output.close(); // Close the file after writing
}
// 读取单词符号序列（tokens）

vector<string> parse_tokens(const char *filename)
{
    ifstream file(filename);
    if (!file.is_open())
    {
        cout << "can not open the file: " << filename << endl;
        exit(1);
    }
    vector<string> tokens;
    string line;
    // string _FLOAT = "FLOAT",_IDN="IDN",_INT="INT";
    //  逐行读取 tokens流
    while (getline(file, line))
    {
        stringstream ss(line);
        string token, type_content;
        getline(ss, token, '\t');       // Extract the token
        getline(ss, type_content, ' '); // Extract the type and content
        if (type_content.find("INT") != string::npos)
        {
            tokens.push_back("INT");
        }
        else if (type_content.find("FLOAT") != string::npos)
        {
            tokens.push_back("FLOAT");
        }
        else if (type_content.find("IDN") != string::npos)
        {
            tokens.push_back("Ident");
        }
        else
            tokens.push_back(token);
    }
    // for (int i=0;i<tokens.size();i++){
    //      cout <<tokens[i]<<endl;
    //  }
    file.close();
    return tokens; // 返回读取到的 token序列
}
int main()
{
    read_grammar();

    compute_first();

    compute_follow();

    construct_goto();

    construct_action();

    // print_slr_table();

    slr_table_to_file("SLR.txt");

    // 读取词法分析器的输出
    vector<string> input_tokens = parse_tokens("./result-lexical/8lex.tsv");

    // for (auto t : input_tokens)
    //     cout << t << endl;

    parse_input(input_tokens); // 根据token流进行移进规约分析并将结果保存在parse_output.txt中

    return 0;
}
